package com.yoshino.leetcode.oneHundred.twentyseventh;

import java.util.ArrayDeque;
import java.util.Deque;

class MaxQueue {

    Deque<Integer> deque;
    Deque<Integer> max;

    public MaxQueue() {
        deque = new ArrayDeque<>();
        max = new ArrayDeque<>();
    }

    public int max_value() {
        return max.isEmpty() ? -1 : max.peek();
    }

    public void push_back(int value) {
        deque.offer(value);
        while (!max.isEmpty() && value > max.peekLast()) {
            max.pollLast();
        }
        max.offer(value);
    }

    public int pop_front() {
        if (deque.isEmpty()) {
            return -1;
        }
        Integer peek = deque.pollFirst();
        if (peek.equals(max.peekFirst())) {
            max.pop();
        }
        return peek;
    }
}